<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>
        红黑树案例一
    </title>
</head>
<body>
    <script>
        // 案例一：依次插入10 9 8 7 6 5 4 3 2 1
        // 1. 插入10
        //     1. 创建节点插入节点10 - 节点为红色
        //     2. 不符合规则2 - 根节点必须是黑色
        //     3. 将节点10的颜色改成黑色

        // 2. 插入9
        //     1. 创建节点插入9 - 节点9为红色
        //     2. 符合规则2
        //     3. 叶子节点添加nil

        // 3. 插入8
        //     1. 创建节点插入8 - 节点8为红色
        //     2. 此时属于情况4：父红祖黑叔黑
        //     3. 
        //     4. 变色
            //     4.1 父变黑
            //     4.2 祖变红
            // 5. 右旋转 - 此时根节点为9
            // 6. 叶子节点添加nil

        // 4. 插入7
        //     1. 创建节点插入7 - 节点为红色
        //     2. 此时属于情况3：父红叔红祖黑
        //     3. 变色
        //         3.1 父变黑
        //         3.2 叔变黑
        //         3.3 祖变红
        //     5. 问题：不符合规则2 - 根节点为黑色
        //     6. 将根节点变为黑色

        // 5. 插入6
        //     1. 插入6
        //     2. 不符合规则4 - 两个红色节点相连
        //     3. 此时属于情况4：父红祖黑叔黑
        //     4. 变色
        //         4.1 父变黑
        //         4.2 祖变红
        //     5. 右旋转
        //     6. 叶子节点添加nil

        // 6. 插入5
        //     1. 创建节点插入5
        //     2. 不符合规则4 - 两个红色节点相连
        //     3. 此时属于情况3：父红叔红祖黑
        //     4. 变色
        //         4.1 父变黑
        //         4.2 叔变黑
        //         4.3 祖变红
        //     5. 左旋转
        //     6. 叶子节点添加nil

        // 7. 插入4
        //     1. 创建节点插入4
        //     2. 不符合规则4 - 两个红色节点相连
        //     3. 此时属于情况4：父红祖黑叔黑
        //     4. 变色
        //         4.1 父变黑
        //         4.2 祖变红
        //     5. 右旋转
        //     6. 叶子节点添加nil

        // 8. 插入3
        //     1. 创建节点插入3
        //     2. 不符合规则4 - 两个红色节点相连
        //     3. 此时属于情况3：父红叔红祖黑
        //     4. 变色
        //         4.1 父变黑
        //         4.2 叔变黑
        //         4.3 祖变红
        //     5. 不符合规则4 - 两个红色节点相连
        //     6. 此时属于情况4：父红祖黑叔黑
        //     7. 变色 - 以节点5为插入项
        //         7.1 父变黑
        //         7.2 祖变红
        //     8. 右旋转 - 以插入节点5的父节点为轴心旋转
        //     9. 叶子节点添加nil

        // 9. 插入2
        //     1. 创建节点插入2
        //     2. 不符合规则4 - 两个红色节点相连
        //     3. 此时属于情况4：父红祖黑叔黑
        //     4. 变色
        //         4.1 父变黑
        //         4.2 祖变红
        //     5. 右旋转 - 以插入节点2的父节点3位轴心旋转
        //     6. 叶子节点添加nil

        // 10. 插入1
        //     1. 创建节点插入1
        //     2. 不符合规则4 - 两个红色节点相连
        //     3. 此时属于情况3：父红叔红祖黑
        //     4. 变色
        //         4.1 父变黑
        //         4.2 叔变黑
        //         4.3 祖变红
        //     5. 不符合规则4 - 两个红色节点相连
        //     6. 此时属于情况3：父红叔红祖黑
        //     7. 变色
        //         7.1 父变黑
        //         7.2 叔变黑
        //         7.3 祖变红
        //     8. 不符合规则2 - 根节点必须为黑色
        //     9. 将根节点改为黑色

    </script>
</body>
</html>